﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0112_IsValid : IAlgorithm
    {
        // 20. 有效的括号

        // 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

        // 有效字符串需满足：
        //  左括号必须用相同类型的右括号闭合。
        //  左括号必须以正确的顺序闭合。

        // 提示：
        //  1 <= s.length <= 10^4
        //  s 仅由括号 '()[]{}' 组成

        public void Test()
        {
            // 算法参数定义
            string s = "([)]";
            // 算法执行与打印
            Console.WriteLine(IsValid(s));
        }

        // 算法
        public bool IsValid(string s)
        {
            var len = s.Length;
            if (len % 2 == 1)
                return false;
            var stack = new Stack<char>();
            for (int i = 0; i < len; i++)
            {
                if (s[i] == '(')
                    stack.Push(')');
                else if (s[i] == '[')
                    stack.Push(']');
                else if (s[i] == '{')
                    stack.Push('}');
                else
                    if (stack.Count == 0 || stack.Pop() != s[i])
                        return false;
            }
            if (stack.Count > 0)
                return false;
            else
                return true;
        }
    }
}
